package acwing.图;


import java.util.*;

/**
 * Dijkstra求最短路2
 *
 * @author yang
 * @date 2022/1/8
 */
public class Dijkstra求最短路2 {

    static int N = 100010;
    static int w[] = new int[N];
    static int h[] = new int[N];
    static int e[] = new int[N];
    static int ne[] = new int[N];
    static int idx, n, m, INF = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        Arrays.fill(h, -1);
        n = sc.nextInt();
        m = sc.nextInt();
        while (m-- > 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            add(x,y,z);
        }
        System.out.println(di());
    }

    private static int di() {

        Arrays.fill(dist, INF);
        dist[1] = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)-> a[1] - b[1]);
        queue.add(new int[]{1,0});
        while (!queue.isEmpty()) {
            int[] t = queue.poll();
            int f = t[0]; // 编号
            int s = t[1]; // 距离
            if (st[f]) continue;
            st[f] = true;
            for (int i = h[f]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > s + w[i]) {
                    dist[j] = s + w[i];
                    queue.add(new int[]{j,dist[j]});
                }
            }
        }
        if (dist[n] == INF) return -1;
        return dist[n];

    }

    private static void add(int x, int y, int z) {
        e[idx] = y;
        w[idx] = z;
        ne[idx] = h[x];
        h[x] = idx++;
    }
}




